package base.day06;

import java.util.HashMap;
import java.util.Map;

/**
 * 描述：
 *      设计一种结构，在该结构中有如下三个功能:
 *      1)insert(key)：将某个key加入到该结构，做到不重复加入
 *      2)delete(key)：将原本在结构中的某个key移除。
 *      3)getRandom()：等概率随机返回结构中的任何一个key。
 *     【要求】 Insert、delete和getRandom方法的时间复杂度都是 O(1)
 *     前两点并不复杂，但是要做到第三点不简单
 *
 *     思路：使用两个哈希表：一个用来添加、删除；另一个用来等概率随机返回结构中的任何一个key
 *     一个hash表：key-key，value索引
 *     另一个hash表： key-索引，value-key
 *     我们在往hash表中添加数据的时候，顺便存入它的索引。并且在另一个hash表中逆序存入这个键值对
 *     我们可以用size来维护这个索引，只有中间不存在空档，
 *     那么我们就可以使用Math.random() * size从hash表2中等概率获取key
 *
 *      删除时，为了保证索引的连续性，我们会保存删除的key的索引，
 *      我们会将index-key表中的被删除的索引位置的key与最后一个位置的key交换，然后再将最后那个位置的index-key删除，
 *      这样就可以保证索引的连续性了。
 * @author hl
 * @version 1.0
 * @date 2020/10/28 16:22
 */
public class RandomPool<K> {
    private Map<K,Integer> keyIndexMap;
    private Map<Integer,K> indexKeyMap;
    private int size;
    public RandomPool() {
        keyIndexMap = new HashMap<>();
        indexKeyMap = new HashMap<>();
        size = 0;
    }

    public void add(K key){
        if (!keyIndexMap.containsKey(key)) {
            keyIndexMap.put(key, size);
            indexKeyMap.put(size++,key);
        }
    }
    public void delete(K key){
        if (keyIndexMap.containsKey(key)) {
            int deleteIndex = keyIndexMap.get(key);
            K lastKey = indexKeyMap.get(--size);
            keyIndexMap.put(lastKey,deleteIndex);
            indexKeyMap.put(deleteIndex,lastKey);
            keyIndexMap.remove(key);
            indexKeyMap.remove(size);
        }
    }
    public K getRandomKey(){
        if (size == 0) {
            return null;
        }
        int randomIndex = (int)(Math.random() * size);
        return indexKeyMap.get(randomIndex);
    }
}
